package com.leetcode.partition3;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2021/10/30 8:52
 */
public class LC260只出现一次的数字3 {

    public static int[] singleNumber(int[] nums) {
        //nums = [1, 2, 1, 3, 2, 5] => [001, 010, 001, 011, 010, 101]
        //001 ^ 001 ^ 010 ^ 010 ^ 011 ^ 101 = 110，110也是两个只出现1次的数字的异或结果
        //找到110的最低1位h=010，根据h将nums分为两组，如果h & n == 0就到a组，否则就到b组
        //a组：001、001、101    b组：010、011、010
        //对a、b两组分别进行异或找到只出现一次的数字
        int[] answer = new int[2];
        int res = 0, low = 1;
        //全员异或，得到答案的两个异或值
        for (int n : nums) res ^= n;
        //找出低位1
        while ((low & res) == 0) low <<= 1;
        //根据低位1将nums分为两组
        for (int n : nums) {
            if ((n & low) == 0) answer[0] ^= n;
            else answer[1] ^= n;
        }
        return answer;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 1, 3, 2, 5};
        System.out.println(Arrays.toString(singleNumber(nums)));
    }

    private static int[] hashtable(int[] nums) {
        int[] answer = new int[2];
        Map<Integer, Integer> numToCount = new HashMap<>();
        for (int num : nums) {
            numToCount.put(num, numToCount.getOrDefault(num, 0) + 1);
        }
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : numToCount.entrySet()) {
            if (i == 2) break;
            if (entry.getValue() == 1) {
                answer[i++] = entry.getKey();
            }
        }
        return answer;
    }
}
